package com.lwl.Algorithmic_data_structure.class09链表;

import com.lwl.Utils.LLinkNode;

/**
 * 给一个l1l2l3l4r1r2r3r4的链表
 * 将其改为 l1r4l2r3...的形式
 */
public class MixLink {

    public static void main(String[] args) {
        LLinkNode link = LLinkNode.createRandomLink();
        link.printLinkList();
        LLinkNode res = mixLink(link);
        res.printLinkList();
        // 最后还要把链表改回来
    }

    public static LLinkNode mixLink(LLinkNode head) {
        LLinkNode slow = head;
        LLinkNode fast = head;
        boolean slowFlag = false;
        while (fast.next != null) {
            fast = fast.next;
            if (slowFlag) {
                slow = slow.next;
            }
            slowFlag = !slowFlag;
        }

        System.out.println(slow.value);

        LLinkNode pre = null;
        LLinkNode t;
        // 接下来对后半段的进行逆序
        while (slow != null) {
            t = slow.next;
            slow.next = pre;
            pre = slow;
            slow = t;
        }
        LLinkNode start = head;
        LLinkNode end = pre;
        // 开始穿插，此时pre为链表尾节点
        while (start != null) {
            LLinkNode s1 = start.next;
            LLinkNode e1 = end.next;
            start.next = end;
            end.next = s1;
            start = s1;
            end = e1;
        }
        return head;
    }
    /*

    node1 -> node2 -> node3 -> node4



     */

}
